Search for: All records

In this paper, we propose a general framework to design efficient polynomial-time approximation schemes (EPTASs) for fundamental stochastic combinatorial optimization problems. Technically speaking, our approach relies on presenting tailor-made reductions to a newly introduced multidimensional Santa Claus problem. Even though the single-dimensional version of this problem is already known to be APX-Hard, we prove that an EPTAS can be designed for a constant number of machines and dimensions, which hold for each of our applications. To demonstrate the versatility of our framework, we first study selection-stopping settings to derive an EPTAS for the free-order prophets problem and for its cost-driven generalization, Pandora’s box with commitment. These results constitute the first approximation schemes in the nonadaptive setting and improve on known inefficient polynomial-time approximation schemes (PTASs) for their adaptive variants. Next, turning our attention to stochastic probing problems, we obtain an EPTAS for the adaptive ProbeMax problem as well as for its nonadaptive counterpart. In both cases, state-of-the-art approximability results have been inefficient PTASs (Chen et al. [25], Fu et al. [35]). Funding: This work was supported by the National Science Foundation, Division of Computing and Communication Foundations [Grants 2327010 and 2440113]. 

Motivated by modern-day applications such as attended home delivery and preference-based group scheduling, where decision makers wish to steer a large number of customers toward choosing the exact same alternative, we introduce a novel class of assortment optimization problems, referred to as maximum load assortment optimization. In such settings, given a universe of substitutable products, we are facing a stream of customers, each choosing between either selecting a product out of an offered assortment or opting to leave without making a selection. Assuming that these decisions are governed by the multinomial logit choice model, we define the random load of any underlying product as the total number of customers who select it. Our objective is to offer an assortment of products to each customer so that the expected maximum load across all products is maximized. We consider both static and dynamic formulations of the maximum load assortment optimization problem. In the static setting, a single offer set is carried throughout the entire process of customer arrivals, whereas in the dynamic setting, the decision maker offers a personalized assortment to each customer, based on the entire information available at that time. As can only be expected, both formulations present a wide range of computational challenges and analytical questions. The main contribution of this paper resides in proposing efficient algorithmic approaches for computing near-optimal static and dynamic assortment policies. In particular, we develop a polynomial time approximation scheme for the static problem formulation. Additionally, we demonstrate that an elegant policy utilizing weight-ordered assortments yields a 1/2 approximation. Concurrently, we prove that such policies are sufficiently strong to provide a 1/4 approximation with respect to the dynamic formulation, establishing a constant factor bound on its adaptivity gap. Finally, we design an adaptive policy whose expected maximum load is within factor 1-\epsilon of optimal, admitting a quasi-polynomial time implementation.